﻿// 快速排序挖坑法
void quicksort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int begin = left;
	int end = right;

	int hole = left;
	int key = arr[hole];

	while (left < right)
	{
		while (left < right && arr[right] >= key)
		{
			right--;
		}
		arr[hole] = arr[right];
		hole = right;
		while (left < right && arr[left] <= key)
		{
			left++;
		}
		arr[hole] = arr[left];
		hole = left;
	}
	arr[hole] = key;
	quicksort(arr, begin, hole - 1);
	quicksort(arr, hole + 1, end);
}